"""
搜索插入位置

问题： 给定一个排序数组和一个目标值，如果找到目标值，则返回其索引。如果没有找到，则返回按顺序插入目标值时应插入的索引位置。
你可以假设数组中不存在重复元素。

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

使用二分查找
# class Solution:
#
#     本类提供了一个方法来搜索给定列表中特定目标值的位置或其应插入的位置。
#
#
#     def search_insert(self, nums, target):
#
#         搜索目标值在列表中的索引位置或其应插入的位置。
#
#         参数:
#         nums (List[int]): 一个已排序的整数列表。
#         target (int): 需要搜索的目标值。
#
#         返回:
#         int: 目标值在列表中或应插入的索引位置。
#
#         # 初始化左右指针
#         left,right = 0, len(nums) - 1
#
#         # 当左指针不大于右指针时，执行二分查找
#         while left <=right:
#             # 计算中间位置
#             mid = (left+right)//2
#
#             # 如果中间位置的值等于目标值，返回该位置
#             if nums[mid] == target:
#                 return mid
#             # 如果中间位置的值小于目标值，移动左指针
#             elif nums[mid] < target:
#                 left = mid + 1
#             # 如果中间位置的值大于目标值，移动右指针
#             else:
#                 right = mid - 1
#
#         # 如果没有找到目标值，返回应插入的位置
#         return left
nums = [1, 3, 5, 6]
print(Solution().search_insert(nums, 5))

猜数问题
我们正在玩猜数字游戏。游戏规则如下：我从 1 到 n 中选一个数字。你必须猜出我选的是哪个数字。每次你猜错时，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的 API guess(int num)，它会返回 3 种可能的结果（-1、1 或 0）：

-1：我选的数字比你猜的小
1：我选的数字比你猜的大
0：恭喜！你猜对了！

示例：
n = 10，我选了 6。
返回 6。

这里有个陷阱 如果返回是-1 说明数小，我们猜测的数值大
def guess(num):
    pass


class Solution:
    def guessNumber(self, n):
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            res = guess(mid)

            if res == 0:
                return mid
            elif res == 1:
                left = mid + 1
            else:
                right = mid - 1

        return left

问题 :
假设一个有序数组在某个未知的枢轴点处发生旋转。
（即，0 1 2 4 5 6 7 可能变为 4 5 6 7 0 1 2）。
给定一个目标值进行查找。如果在数组中找到该目标值，则返回其索引，否则返回 -1。
假设数组中不存在重复元素。

思路
这个问题是二分查找的变种，它这里唯一的一个小trick就是把本来有序的数组做了一个旋转。但是注意，旋转的2部分是分别有序的。

还有一个很重要的特点：后半部分小于前半部分，所以其实很容易判断出mid在哪一部分。

（如果num[mid] > num[0]，我们就知道mid在左部分，否则在右部分。）

这里不能直接用二分的问题在于：如果target和mid不在同一部，就会出错。

举例nums: [4,5,6,1,2,3,4]，st = 0 ， ed = 6，mid = 3, target = 6

此时：mid指向1，而target是6，说明mid和target不在同一部，会出现什么问题呢？
按照算法：

if (nums[mid] < target)
  st = mid+1
这里，明明应该往左搜索，但是却往右边搜索了。 所以，为了解决这个问题。我们可以引入inf和-inf

如何知道在哪一段？
如果target < nums[0]和nums[mid]<nums[0]同时成立，那么我们按照普通的二分查找操作就行。
如果target < nums[0]和nums[mid]<nums[0]不同时成立，那么说明target和mid在不同部分。我们需要根据target的情况引入inf和-inf
如果target < nums[0]，说明在右部，我们引入-inf，让st移动
否则，说明在左部，我们引入inf，让ed移动


"""
class Solution:
    """
    本类提供了一个方法来在旋转排序数组中寻找特定目标值的索引位置。
    旋转排序数组是指原数组为非递减数组，经过若干次旋转后形成的数组。
    """

    def search_target(self, nums, target):
        """
        在旋转排序数组中寻找特定目标值的索引位置。

        参数:
        nums (List[int]): 旋转排序后的数组。
        target (int): 需要寻找的目标值。

        返回:
        int: 目标值在数组中的索引位置，如果不存在则返回-1。
        """

        # 获取数组长度
        n = len(nums)
        # 初始化左右指针
        left, right = 0, n - 1

        # 当左指针没有越过右指针时，执行二分查找
        while left <= right:
            # 计算中间位置，避免整数溢出
            mid = left + (right - left) // 2
            # 如果中间值等于目标值，返回中间值的索引
            if nums[mid] == target:
                return mid

            # 判断中间值是否在左半部分
            mid_in_left = nums[mid] >= nums[0]
            # 判断目标值是否在左半部分
            target_in_left = target >= nums[0]

            # 如果中间值和目标值在同一部分（要么都在左半部分，要么都在右半部分）
            if (mid_in_left and target_in_left) or (not mid_in_left and not target_in_left):
                # 如果中间值大于目标值，调整右指针
                if nums[mid] > target:
                    right = mid - 1
                else:
                    # 否则调整左指针
                    left = mid + 1
            else:
                # 如果中间值和目标值不在同一部分
                if target_in_left:
                    # 如果目标值在左半部分，调整右指针
                    right = mid - 1
                else:
                    # 否则调整左指针
                    left = mid - 1
        # 如果没有找到目标值，返回-1
        return -1




if __name__ == '__main__':
    pass
